home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1 / Nebula One.iso / Graphics / 2D_3D / 2DLab / README < prev   
Encoding:
Text File  |  1995-06-12  |  5.8 KB  |  134 lines
  1. README - 9/91 PJF
  2.  
  3. This directory contains sources for 2DLab, an interactive tool
  4. for visualizing some common geometric algorithms.
  5.  
  6. The source code for Voronoi diagrams and Delaunay tesselations
  7. was writen by Seth Teller (of SGI?) and available on many archive
  8. sites.
  9.  
  10. Ignore the warning messages that appear during compilation.
  11.  
  12. ------------- Info from Help window ---------------------------
  13. 2DLab animates a few algorithms from computational geometry.  It
  14. was originally released in early 1990, back when I was a graduate
  15. student at Michigan State University.  In the process of updating
  16. the program for 2.0, things changed substantially, and many features
  17. were added.  I hope you like the program.
  18.  
  19. Running the program
  20. Two windows will appear when 2DLab is fired up.  The Geometry Window
  21. contains the data and the results of any algorithms run on the
  22. data.  The 2DLab Control window allows you to configure the data
  23. set, the algorithm, and the drawing that takes place.
  24.  
  25. When the program is invoked, the Geometry Window will contain ten
  26. points, and the selected algorithm (Prim's MST algorithm by default)
  27. will be applied to these points.  New points can be created by
  28. clicking in the window.  There is a `margin' around the border of
  29. the window  within which points will not be displayed, so If you
  30. click the mouse button and no point appears, you're probably too
  31. close to the edge (this margin was put in to make the Voronoi
  32. tesselation have a nice border.
  33.  
  34. A new set of random points (uniformly distributed within the window's
  35. usable region) can be generated by entering the desired number of
  36. points in the editable text field and pressing the Generate button.
  37.  
  38. The highlighted button in the RadioButton array in the Control
  39. Window identifies the particular algorithm to be `animated.'
  40.  
  41. The Anim/Disp button will run the appropriate animation when pressed.
  42. The Disp button will simply display the resulting data structure without
  43. animating.  It only works when the data structure has already been previously
  44. computed (i.e. ya gotta Anim before you can Disp).
  45. The Auto-Go checkbox specifies the program's behavior when new
  46. points are created with the mouse.  If the box is checked, the
  47. selected algorithm is run immediately when a new point is added.
  48.  
  49. The three color wells allow you to pick background, foreground,
  50. and highlighting colors.  When the display is drawn, points and
  51. line segments appear in the foreground color.  During animation,
  52. transient drawing is done using the highlight color.  By default,
  53. these colors are white, black, and  67% gray, respectively.  You
  54. can set them to anything you want using the standard color well
  55. tricks.
  56.  
  57. The line width slider controls how thickly everything is drawn (both
  58. points and lines).
  59.  
  60. The `Status' item displays informative (?) messages about the
  61. progress of the algorithm currently being animated, the drawing
  62. taking place, etc.
  63.  
  64. The Document menu allows you to save the current data set in a
  65. `generic' form, load a similarly-formatted file in for animation,
  66. and save the generated imagery as TIFF or EPS.  The file format
  67. for the data is simple.  The first number is the number of ordered
  68. pairs (%d), and the remaining numbers are the pairs (%f %f).  The error
  69. checking for I/O is pathetic, so please feed 2DLab well-behaved data files.
  70.  
  71. The Copy item of the Edit menu may be selected.  It sticks the contents of
  72. the Geometry window in the pasteboard.
  73.  
  74. Algorithms
  75. In the following brief descriptions, N is the number of 2D points,
  76. and the O-notation refers to time complexity rather than space
  77. complexity.  When the algorithms are invoked, those with quick eyes
  78. will notice some graphical razzle-dazzle as the data structure is
  79. constructed.  After the algorithm has completed, the `resulting'
  80. data structure will remain in the window.
  81.  
  82. - Prim's O(N^2) Minimal Spanning Tree (MST) algorithm.
  83.  
  84. - Kruskal's O(E log E) MST algorithm. WARNING: the implementation
  85. in this program is NOT optimal (it's actually O(N^2)).  Anybody
  86. who wants to hack together the priority queue stuff to implement
  87. the optimal algorithm is free to do so (lazy, that's me).
  88.  
  89. - Jarvis' O(N log N) convex hull construction algorithm.
  90.  
  91. - Graham's O(N log N) convex hull construction algorithm.
  92.  
  93. - Somebody's O(N log N) Voronoi diagram algorithm.
  94.  
  95. - Somebody's O(N log N) Delaunay triangulation algorithm.  (code
  96. for these last two algorithms was written by Seth Teller, who
  97. apparently used Fortune's netlib code as a basis).
  98.  
  99. - my own Gabriel Graph construction algorithm (it uses the
  100. Delaunay triangulation as a starting point).
  101.  
  102. - my own Relative Neighborhood Graph construction algorithm (again,
  103. using the Delaunay triangulation as a starting point).
  104.  
  105. Those interested in the details of the algorithms should refer to
  106. Preparata and Shamos' book on computational geometry.  Sedgewick's
  107. book also has covers geometric algorithms.  The GG and RNG haven't
  108. been used much, and are a little harder to find in the literature.
  109. Consult Toussaint, `The relative neighborhood graph of a finite
  110. point set', Pattern Recognition 12, 261-268 for info about the RNG.
  111. The Gabriel graph was used in Matula and Sokal, `Properties of
  112. Gabriel Graphs Relevant to Geographic Variation Research and the
  113. Clustering of Points in the Plane', Geographical Analysis 12,
  114. 205-222.   However, I don't have either of those papers in my
  115. posession.  This software was based on the discussion in Tuceryan
  116. and Chorzempa, `Relative Sensitivity of a family of closest-point
  117. graphs in computer vision applications', Pattern Recognition 24,
  118. 361-374.
  119.  
  120. About the author; feedback
  121. This program was written by:
  122.  
  123. Patrick Flynn
  124. Assistant Professor
  125. School of Electrical Engineering and Computer Science
  126. Washingon State University
  127. Pullman, WA 99164-2752
  128. (flynn@eecs.wsu.edu)
  129.  
  130. If you find bugs, let me know.
  131. If you add functionality, let me know.
  132. If you like/hate it and just want to tell me, let me know.
  133. Date: 9/91
  134.